(defvar *testing_data2* 
'((3) (7 5) (2 4 6) (8 5 9 3)))


(defvar *testing_data* 
'((75)
(95 64)
(17 47 82)
(18 35 87 10)
(20 04 82 47 65)
(19 01 23 75 03 34)
(88 02 77 73 07 63 67)
(99 65 04 28 06 16 70 92)
(41 41 26 56 83 40 80 70 33)
(41 48 72 33 47 32 37 16 94 29)
(53 71 44 65 25 43 91 52 97 51 14)
(70 11 33 28 77 73 17 78 39 68 17 57)
(91 71 52 38 17 14 91 43 58 50 27 29 48)
(63 66 04 68 89 53 67 30 73 16 69 87 40 31)
(04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)))


  
(defun p18-r ()
  (apply
	'+
	(mapcar
	  (lambda (x)
		(cadr x))
	  (p18))))

(defun p18 ()
  (defun p18-inner (data column)
    ;(format t "~a~%" column)
	(if (null data)
	    column
		(p18-inner (cdr data) (append column (tmp (caar (last column)) (car data))))))
  (p18-inner (cdr *testing_data*) '((0 0) (1 75))))

(defun tmp (column items)
  ;(format t "~a~%" column)
  (let ((a column)
		 (b (1+ column)))
	;(format t "~a,~a~%" (n-th-item a items) (n-th-item b items)))) 
       (if (> (n-th-item a items) (n-th-item b items))
		   (list (list a (n-th-item a items)))
		   (list (list b (n-th-item b items))))))

(defun n-th-item (column items)
  (nth (1- column) items))

(defun range (start end)
        (loop for i from start below end collect i)) 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun max-list (l)
(labels ((max-list-rec (lst res)
(if (not (second lst))
res
(max-list-rec (cdr lst)
(push (max (first lst) (second lst)) res)))))
(if (not (second l))
(first l)
(max-list-rec (reverse l) '()))))

(defun list-add (a b)
(if (or (not a)
(not b))
'()
(cons (+ (car a)
(car b))
(list-add (cdr a) (cdr b)))))

(defun max-sum (lst)
(let ((sum (make-list (list-length (first (last lst))) :initial-element 0)))
(loop for a in (reverse lst)
do (setf sum (max-list (list-add a sum))))
sum)) 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(format t "~a~%" *testing_data*)
;(format t "~a~%" (p18))
(format t "~a~%" (time (p18-r)))
(format t "~a~%" (time (max-sum *testing_data*)))
;(format t "~a~%" (tmp 1 '(7 5)))
